package com.kehao.leetcode.middle.sort_search;

import org.junit.Test;

public class RotateSortedArraySearchSolution {
    public int search(int[] nums, int target) {
        int minPos = getMinPos(nums);
        int leftFake =0,rightFake = nums.length-1;
        int midFake = (leftFake+rightFake)/2;
        int distance = minPos;
        int midReal = (midFake+distance)%nums.length;
        while (leftFake<=rightFake){
           if(nums[midReal]==target){
               return midReal;
           }else if(nums[midReal]<target){
               leftFake = midFake+1;
           }else {
               rightFake = midFake-1;
           }
            midFake = (leftFake+rightFake)/2;
            midReal = (midFake+distance)%nums.length;
        }
        return -1;
    }



    private int getMinPos(int[] nums){
        if(nums.length==1) return 0;
        if(nums.length==2) return nums[0]<nums[1]?0:1;
        int left =0,right =nums.length-1;
        int mid = (left+right)/2;
        while (left<right){
            if(nums[mid]<nums[mid-1]&&nums[mid]<nums[mid+1]){
                return mid;
            }else if (nums[mid]>nums[mid-1]&&nums[mid]>nums[mid+1]){
                return mid+1;
            }else {
                if(nums[left]<nums[mid]){
                    if(nums[mid]< nums[right]){
                        return left;
                    }else {
                        left = mid;
                        mid = (left+right)/2;
                    }
                }else {//nums[left]>nums[mid]
                    if(nums[mid]>nums[right]){
                        return right;
                    }else {
                        right = mid;
                        mid = (left+right)/2;
                    }
                }
            }
        }
        return -1;
    }

    @Test
    public void test01(){
        int [] nums = {4,5,6,7,0,1,2};
        System.out.println(search(nums,0));
    }

    @Test
    public void test02(){
        int [] nums = {4,5,6,7,0,1,2};
        System.out.println(search(nums,3));
    }

    @Test
    public void test03(){
        int [] nums = {1,3};
        System.out.println(search(nums,0));
    }

    @Test
    public void test04(){
        int [] nums = {1,3,5};
        System.out.println(search(nums,0));
    }
}
